package com.c5p1ng.linkedlist;

/**
 * 1) 单链表反转
 * 2) 链表中环的检测
 * 3) 两个有序的链表合并
 * 4) 删除链表倒数第n个结点
 * 5) 求链表的中间结点
 *
 */
public class LinkedListAlgo {

    /**
     * 单链表反转
     * @param list
     */
    public static Node reverse(Node list) {
        Node curr = list, pre = null;
        while (curr != null) {
            Node next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    /**
     * 链表中环的检测
     * @param list
     */
    public static boolean checkCircle(Node list) {
        if (list == null) return false;
        Node fast = list;
        Node slow = list;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 两个有序的链表合并
     * @param l1
     * @param l2
     * @return
     */
    public static Node mergeTwoLists(Node l1, Node l2) {
        Node soldier = new Node(0, null);//使用哨兵节点
        Node p = soldier;
        while (l1 != null && l2 != null) {
            if(l1.data < l2.data) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        }
        if(l2 != null) {
            p.next = l2;
        }
        return soldier.next;
    }

    public static void main(String[] args) {
        Node head = createNode(1);
        head.next = createNode(2);
        head.next.next = createNode(3);
        printAll(reverse(head));

        Node list = createNode(1);
        list.next = createNode(2);
        list.next.next = createNode(3);
        list.next.next.next = list;
        System.out.println(checkCircle(list));

        Node list1 = createNode(3);
        list1.next = createNode(5);
        list1.next.next = createNode(8);
        Node list2 = createNode(2);
        list2.next = createNode(6);
        list2.next.next = createNode(9);
        printAll(mergeTwoLists(list1, list2));
    }

    public static Node createNode(int value) {
        return new Node(value, null);
    }

    public static void printAll(Node list) {
        Node p = list;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }
}
